home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 154_01 / xref.c < prev    next >
Text File  |  1980-01-01  |  4KB  |  185 lines
  1. /*
  2.  *   xref.c:    word-to-line cross-reference -
  3.  *     usage:      xref [file]  (defaults to standard input)
  4.  *     note:       A "word" is defined by the macro "okchar(c)" 
  5.  *
  6.  *   (c) Chuck Allison, 1985
  7.  *
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <ctype.h>
  12.  
  13. #ifdef MICROSOFT
  14.  
  15. #include <malloc.h>
  16.  
  17. #define        getmem        malloc
  18. #define        chk_ferror    fprintf
  19.  
  20. #endif
  21.  
  22. #define okchar(c)  (isalnum(c) || c == '-' || c == '\'')
  23. #define MAXLINE 512
  24.  
  25. /* ..Linked-list structure for each list of line numbers.. */
  26. struct list
  27. {
  28.     struct list *next;
  29.     int lnum;
  30. } *addline();
  31.  
  32. /* ..Node structure for tree of distinct words.. */
  33. struct tree
  34. {
  35.     char *word;
  36.     struct tree *left,*right;
  37.     struct list *lptr;       /* -> to list of line #'s for this word */
  38. } *words = NULL, *node, *addword(), *find_node();
  39.  
  40. char *lineptr, *getword(), *getmem();
  41. int  distinct = 0;
  42.  
  43.  
  44. main(argc,argv)
  45. int argc;
  46. char *argv[];
  47. {
  48.     register lineno = 0;
  49.     static char linebuf[MAXLINE], wordbuf[MAXLINE];
  50.     
  51.     /* ..Get optional filename.. */
  52.     if (argc > 1)
  53.         if (freopen(argv[1],"r",stdin) == NULL)
  54.         {
  55.             printf("---> ERROR: can't open %s\n",argv[1]);
  56.             exit(1);
  57.         }
  58.         else
  59.             fputs("reading file ...\n",stderr);
  60.     else
  61.             fputs("Enter data:\n\n",stderr);
  62.  
  63.     /* ..Process each line of text file.. */
  64.     while (fgets(linebuf,MAXLINE,stdin))
  65.     {
  66.         ++lineno;                  /* ..we just read another line.. */
  67.         lineptr = linebuf;         /* ..point to start of line.. */
  68.         while (getword(wordbuf))
  69.         {
  70.             /* ..add to tree.. */
  71.             words = addword(words,wordbuf);
  72.  
  73.             /* ..get list header for this word's line numbers.. */
  74.             node = find_node(words,wordbuf);
  75.  
  76.             /* ..add this line to list of line numbers.. */
  77.             node->lptr = addline(node->lptr,lineno);
  78.         }
  79.     }
  80.  
  81.     fprintf(stderr,"No. of distinct words: %d\n\n",distinct);
  82.     print_tree(words);
  83. }
  84.  
  85.  
  86. char *getword(s)          /* ..get next word from line buffer.. */
  87. char *s;
  88. {
  89.     register char *wordptr = s;
  90.  
  91.     /* ..Ignore unwanted characters.. */
  92.     while (*lineptr && !okchar(*lineptr))
  93.         ++lineptr;
  94.  
  95.     /* ..Build word.. */
  96.     while (okchar(*lineptr))
  97.     {
  98.         *wordptr++ = tolower(*lineptr);
  99.     lineptr++;
  100.     };
  101.     *wordptr = '\0';
  102.     return strlen(s) ? s : NULL;
  103. }
  104.  
  105. struct tree *addword(t,word)     /* ..add word to list (if new).. */
  106. struct tree *t;
  107. char *word;
  108. {
  109.     if (t == NULL)
  110.     {
  111.         /* ..new entry.. */
  112.         ++distinct;
  113.         t = (struct tree *) getmem(sizeof(struct tree));
  114.         t->word = (char *) getmem((strlen(word)+1)*sizeof(char));
  115.         strcpy(t->word,word);
  116.         t->left = t->right = (struct tree *) NULL;
  117.         t->lptr = (struct list *) NULL;
  118.     }
  119.     else if (strcmp(t->word,word) < 0)
  120.         t->right = addword(t->right,word);
  121.     else if (strcmp(t->word,word) > 0)
  122.         t->left = addword(t->left,word);
  123.  
  124.     return t;
  125. }
  126.  
  127. struct list *addline(p,n)       /* ..add line # for current word.. */
  128. struct list *p;
  129. int n;
  130. {
  131.     struct list *q;
  132.     
  133.     if (p == NULL)
  134.     {
  135.         /* ..insert at tail.. */
  136.         q = (struct list *) getmem(sizeof(struct list));
  137.         q->lnum = n;
  138.         q->next = (struct list *) NULL;
  139.         return q;
  140.     }
  141.     else if (p->lnum != n)
  142.         /* ..keep looking.. */
  143.         p->next = addline(p->next,n);
  144.  
  145.     return p;
  146. }
  147.  
  148. print_tree(t)
  149. struct tree *t;
  150. {
  151.     if (t != NULL)
  152.     {
  153.         print_tree(t->left);
  154.         printf("%-20.20s: ",t->word);
  155.         chk_ferror(stdout,"standard output");
  156.         print_list(t->lptr); putchar('\n');
  157.         print_tree(t->right);
  158.     }
  159. }
  160.  
  161. print_list(p)
  162. struct list *p;
  163. {
  164.     register count;
  165.     
  166.     for (count = 0; p != NULL; p = p->next, ++count)
  167.     {
  168.         printf("%5d",p->lnum);
  169.         if ((count+1)%10 == 0 && p->next != NULL)
  170.             printf("\n%22c",' ');
  171.     }
  172. }
  173.  
  174. struct tree *find_node(p,s)
  175. struct tree *p;
  176. char *s;
  177. {
  178.     if (strcmp(p->word,s) > 0)
  179.         return find_node(p->left,s);
  180.     else if (strcmp(p->word,s) < 0)
  181.         return find_node(p->right,s);
  182.     else
  183.         return p;       /* .."s" is guaranteed to be found.. */
  184. }
  185.